package lc264;
//给你一个整数 n ，请你找出并返回第 n 个 丑数 。
//
// 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
//
//
//
// 示例 1：
//
//
//输入：n = 10
//输出：12
//解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：1
//解释：1 通常被视为丑数。
//
//
//
//
// 提示：
//
//
// 1 <= n <= 1690
//
// Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 767 👎 0

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    /**
     * 264. 丑数 II
     * <a href="https://leetcode-cn.com/problems/ugly-number-ii/"/>
     * 贪心算法，把所有的数据存起来，然后排序，获取下标就是结果
     * time:O(NLogN)
     * space:O(N)
     * spend: 15m
     */
    public int nthUglyNumber(int n) {
        List<Long> nthUglyNumList = new ArrayList<>();
        int max = Integer.MAX_VALUE;
        for(long a = 1L; a <= max; a *= 2){
            for(long b = a; b <= max; b *= 3){
                for(long c = b; c <= max; c *= 5){
                    nthUglyNumList.add(c);
                }
            }
        }
        nthUglyNumList.sort(Long::compare);
        return nthUglyNumList.get(n - 1).intValue();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int i = solution.nthUglyNumber(10);
        System.out.println(i);
    }

}
//leetcode submit region end(Prohibit modification and deletion)
